/**
 * 
 */
package leetCode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;

/**
 * @author zhong
 *
 */
public class CrackingtheSafe {
	class Node {
		Node[] neib;
		boolean visited;

		/**
		 * 新建一个有k个子节点的节点
		 * 
		 * @param k
		 */
		public Node(int k) {
			neib = new Node[k];
		}
	}

	int minLen = Integer.MAX_VALUE;
	String reString = "";

	public String crackSafe(int n, int k) {
		// 构造一颗前缀树
		Node root = new Node(k);
		Queue<Node> queue = new LinkedList<>();
		queue.add(root);
		for (int i = 0; i < n + 1; i++) {// n曾的节点
			int size = queue.size();
			for (int j = 0; j < size; j++) {
				Node cur = queue.poll();
				for (int l = 0; l < k; l++) {
					cur.neib[l] = new Node(k);
					queue.add(cur.neib[l]);
				}
			}
		}
		StringBuilder sBuilder = new StringBuilder();
		// dfs(sBuilder, 0, (int) Math.pow(k, n), n, k, root, 0);
		// return reString;
		Set<String> visited = new HashSet<>();
		for (int i = 0; i < n; i++) {
			sBuilder.append('0');
		}
		visited.add(sBuilder.toString());
		dfs(sBuilder, (int) Math.pow(k, n), n, k, visited);
		return reString;
		// return backtrack(n, k, root);
	}

	private String backtrack(int n, int k, Node root) {
		int i = 0;
		StringBuilder sBuilder = new StringBuilder();
		StringBuilder end = new StringBuilder();
		for (int j = 0; j < n; j++) {
			end.append(k - 1);
		}
		Node cur = root;
		int count = 0;
		int targetCount = (int) Math.pow(k, n);
		int lenRec = Integer.MAX_VALUE;
		String reString = "";
		while (i >= 0) {
			boolean next = false;
			if (i < n - 1) {
				if (sBuilder.substring(0, i + 1).equals(end.substring(0, i + 1))) {// 前面的最后没有需要改变的了
					break;
				}
				next = true;
			} else {
				int j = sBuilder.length() - n + 1;
				cur = root;
				while (j < sBuilder.length()) {
					cur = cur.neib[sBuilder.charAt(j) - '0'];
					j++;
				}
				for (Node node : cur.neib) {// 存在一个没有访问过的子节点，则可以继续走
					if (!node.visited) {
						next = true;
						break;
					}
				}
			}
			if (next) {// 向前走
				if (i < n - 1) {
					for (int j = 0; j < k; j++) {
						if (sBuilder.length() == i) {
							sBuilder.append(j);
						} else {
							sBuilder.setCharAt(i, (char) (j + '0'));
						}
					}
				} else {
					for (int j = 0; j < k; j++) {
						if (!cur.neib[j].visited) {
							if (sBuilder.length() == i) {
								sBuilder.append(j);
							} else {
								sBuilder.setCharAt(i, (char) (j + '0'));
							}
							count++;
							if (count == targetCount) {
								if (i + 1 < lenRec) {
									lenRec = i + 1;
									reString = sBuilder.substring(0, i + 1);
								}
							} else {
								i++;
							}
						}
					}
				}
			} else {// 回溯
				// 需要把visited置为false
				i--;
			}
		}
		return reString;
	}

	/**
	 * 
	 * @param sBuilder
	 *            当前总共的字符串，也就是 结果
	 * @param targetCount
	 *            目标个数n^k，也就是visited的size应该达到的个数
	 * @param n
	 * @param k
	 * @param visited
	 *            已经访问过的可能密码个数
	 * @return
	 */
	private boolean dfs(StringBuilder sBuilder, int targetCount, int n, int k, Set<String> visited) {
		if (visited.size() == targetCount) {
			if (sBuilder.length() < minLen) {
				minLen = sBuilder.length();
				reString = sBuilder.toString();
			}
			return true;// 增加return，速度块很多，
		} else {
			int curLen = sBuilder.length();
			int start = curLen - n + 1;
			String prev = sBuilder.substring(start, curLen);// 后n-1位字符串
			for (int i = 0; i < k; i++) {
				String code = prev + i;
				if (visited.add(code)) {// 如果没访问过该密码，则加入访问并递归
					sBuilder.append((char) ('0' + i));// 增加刚刚的i
					if (dfs(sBuilder, targetCount, n, k, visited))
						return true;// 如果增加i的深入能够得到目标，则返回true
					visited.remove(code);// 移除刚刚访问的密码
					sBuilder.delete(sBuilder.length() - 1, sBuilder.length());// 删除刚刚的i
				}
			}
		}
		return false;
	}

	private void dfs(StringBuilder sBuilder, int count, int targetCount, int n, int k, Node root, int curLen) {
		// System.out.println(count + " " + sBuilder + " " + sBuilder.substring(0,
		// curLen));
		// if (count == targetCount) {// 当前个数已经满足，则直接返回str
		// if (curLen < minLen) {
		// minLen = curLen;
		// reString = sBuilder.substring(0, curLen);
		// }
		// } else {
		if (curLen >= minLen) {
			return;
		}
		if (curLen < n - 1) {
			if (curLen == sBuilder.length()) {
				sBuilder.append('0');
			}
			for (int i = 0; i < k; i++) {
				sBuilder.setCharAt(curLen, (char) ('0' + i));
				dfs(sBuilder, 0, targetCount, n, k, root, curLen + 1);
			}
		} else {
			// 取最后n-1个字符
			int i = curLen - n + 1;
			Node cur = root;
			while (i < curLen) {
				cur = cur.neib[sBuilder.charAt(i) - '0'];
				i++;
			}
			if (sBuilder.length() == curLen) {
				sBuilder.append('0');
			}
			for (int j = 0; j < k; j++) {
				Node node = cur.neib[j];
				if (!node.visited) {
					node.visited = true;
					sBuilder.setCharAt(curLen, (char) ('0' + j));
					int newCount = count + 1;
					if (newCount == targetCount) {
						if (minLen > curLen + 1) {
							minLen = curLen + 1;
							reString = sBuilder.substring(0, curLen + 1);
						}
						node.visited = false;
						return;// 从当前向下不会有更短的,把刚刚置为true的置为false
					}
					dfs(sBuilder, newCount, targetCount, n, k, root, curLen + 1);
					node.visited = false;
				}
			}
			// }
		}
	}

	public String crackSafeSol1(int n, int k) {
		StringBuilder sBuilder = new StringBuilder();
		for (int i = 0; i < n - 1; i++) {
			sBuilder.append(0);
		}
		String start = sBuilder.toString();
		HashSet<String> visited = new HashSet<>();
		StringBuilder reStringBuilder = new StringBuilder();
		reStringBuilder.append(start);// ?
		dfs(start, k, visited, reStringBuilder);
		System.out.println(start);
		return reStringBuilder.toString();
	}

	/**
	 * start为n-1长度的字符串，
	 * 
	 * @param start
	 * @param k
	 * @param visited
	 * @param res
	 */
	private void dfs(String start, int k, HashSet<String> visited, StringBuilder res) {
		for (int i = 0; i < k; i++) {
			String next = start + i;
			if (visited.add(next)) {// 之前没有见过这个密码
				dfs(next.substring(1), k, visited, res);
				res.append(i);
			}
		}
	}

	public String crackSafe3(int n, int k) {
		final int total = (int) Math.pow(k, n), mod = (int) Math.pow(10, n - 1);
		final Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		map.put(0, 0);
		final Stack<Integer> stack = new Stack<Integer>();
		stack.add(0);
		while (stack.size() != total) {
			int top = stack.peek();
			int prefix = (top % mod) * 10;// 前n-1位
			for (int i = map.get(top); i < k; ++i) {
				int next = prefix + i;
				if (!map.containsKey(next)) {// 新密码
					map.put(top, i + 1);// 后续待处理
					map.put(next, 0);
					stack.push(next);// 后续待处理
					break;
				}
			}
			if (top == stack.peek()) {// 如果是true则说明刚刚没有压入任何next，也就是top没有后续可以处理，从栈和map中移除
				map.remove(top);
				stack.pop();
			}
		}
		final StringBuilder sb = new StringBuilder();
		while (1 != stack.size()) {
			sb.append(stack.pop() % 10);
		}
		return String.format(String.format("%%0%dd", n), stack.pop()) + sb.reverse().toString();
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int n = 1, k = 2;
		System.out.println(new CrackingtheSafe().crackSafe3(n, k));
		// System.out.println(new CrackingtheSafe().crackSafe(n, k));
	}

}
